package forth

/*
	数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

	你可以假设数组是非空的，并且给定的数组总是存在多数元素。

	示例1:
	输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]

	输出: 2
	限制：

	1 <= 数组长度 <= 50000

	来源：力扣（LeetCode）
	链接：https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof
	著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

*/

// 因为是要找到出现次数超过一半的数、也就是说、它出现的次数比其它所有数字出现的次数之和还要多
func majorityElement(nums []int) int {
	result := nums[0]
	times := 1
	for i := 1; i < len(nums); i++ {
		if times == 0 {
			result = nums[i]
			times = 1
			continue
		} else if nums[i] != result {
			times--
		} else {
			times++
		}
	}
	return result
}

// 因为是要找到出现次数超过一半的数、也就是说、它出现的次数比其它所有数字出现的次数之和还要多
func majorityElement1(nums []int) int {
	times := 1
	result := nums[0]
	for i := 1; i < len(nums); i++ {
		if times == 0 {
			result = nums[i]
			times = 1
			continue
		}
		if result == nums[i] {
			times++
		} else {
			times--
		}
	}
	return result
}
